<head>
    <meta charset="UTF-8">
<title>算法提高 递推求值</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>&nbsp;</p>
<p>已知递推公式：</p>
<p>&nbsp;</p>
<p>F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,</p>
<p>&nbsp;</p>
<p>F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.</p>
<p>&nbsp;</p>
<p>初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。<br />
输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以99999999的余数。<br />
【输入格式】<br />
输入第一行包含一个整数n。</p>
<p>&nbsp;</p>
<p>【输出格式】</p>
<p>输出两行，第一行为F(n, 1)除以99999999的余数，第二行为F(n, 2)除以99999999的余数。</p>
<p>【样例输入】<br />
4</p>
<p>&nbsp;</p>
<p>【样例输出】</p>
<p>14</p>
<p>&nbsp;</p>
<p>21</p>
<p>【数据规模和约定】<br />
1&lt;=n&lt;=10^18。</p>